\documentclass[UTF8]{ctexart}
\usepackage{CJK}
\usepackage{indentfirst}
\usepackage{amsmath}
\CTEXsetup[format={\Large\bfseries}]{section}

\title{$LCS$长度递推公式的证明}
\author{张卓涵 \\ 信息与计算科学 \\ 学号：3190101161}
\date{2020.12.29}

\begin{document}
    \maketitle

    \section{定理($theorem$)}
    %\begin{equation}
        $$C[i,j]=
        \begin{cases}
        C[i-1,j-1]+1 & {if\ x[i]=y[j]} \\
        max\{C[i,j-1],\ C[i-1,j]\} & {else} \\
        \end{cases}$$
    %\end{equation}

    \section{证明($proof$)} 
    \hspace{0.2em} 下面，我们只证明$x[i]!=y[j]$的情况。

    
    \hspace{0.2em} 显然，我们有：$$C[i,j]-1<=C[i-1,j]<=C[i,j]$$
    $$C[i,j]-1<=C[i,j-1]<=C[i,j]$$ 不妨假设$C[i-1,j]=C[i,j]-1$，此时
    应有$x[i]=y[k] \in LCS[i,j]$，而$k<j$。那么，对$LCS[i,j-1]$而言，
    去掉$y[j]$后，应该对两个序列的最长子序列没有影响，因为$LCS[i,j]$里并不含
    $y[j]$。所以，$LCS[i,j-1]=LCS[i,j]$，也即$C[i,j-1]=C[i,j]$。


    \hspace{0.2em} 同理，假设$C[i,j-1]=C[i,j]-1$时，有$C[i-1,j]=C[i,j]$。
    也就是说，$C[i-1,j]$与$C[i,j-1]$不会同时等于$C[i,j]-1$，二者中至少有一个
    等于$C[i,j]$，那么有$$C[i,j]=max\{C[i,j-1],\ C[i-1,j]\} \quad (x[i]!=y[j])$$
    成立。
\end{document}